package offer53;

/**
 * https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
 */
class Solution {
    public int find(int[] nums, int start, int end, int target) {
        if (nums[start] == target) {
            //往前找
            int tmp = start;
            while (nums[tmp] == target) {
                tmp -= 1;
            }
            return tmp + 1;
        }
        if (end - start == 1) {
            return -1;
        }
        //找到中位数
        int mid = (start + end) / 2;
        if (nums[mid] > target) {
            return find(nums, mid, end, target);
        } else {
            return find(nums, start, mid, target);
        }

    }

    public int search(int[] nums, int target) {
        int start = find(nums, 0, nums.length - 1, target);
        if (start == -1) {
            return 0;
        }
        int count = 0;

        for (int i = start; i < nums.length - 1; i++) {

            if (nums[i] == target) {
                count++;
            } else {
                break;
            }
        }
        return count;
    }

    public static void main(String[] args) {

    }
}
